package com.congee02.template;

import java.util.List;

public class HasCycle_DFS {

    public boolean hasCycle(List<Integer>[] graph) {

        int n = graph.length;

        boolean[] visited = new boolean[n];
        boolean[] onStack = new boolean[n];

        for (int i = 0 ; i < n ; i ++ ) {
            if (! visited[i] && dfs(graph, visited, onStack, i)) {
                return true;
            }
        }

        return false;
    }

    private boolean dfs(List<Integer>[] graph, boolean[] visited, boolean[] onStack, int cur) {

        visited[cur] = onStack[cur] = true;

        if (graph[cur] == null) {
            onStack[cur] = false;
            return false;
        }

        for (int next : graph[cur]) {

            if (onStack[next]) {
                return true;
            } else if (! visited[next] && dfs(graph, visited, onStack, next)) {
                return true;
            }

        }

        onStack[cur] = false;
        return false;
    }

}
